/*
 * Copyright (c) 1999, 2000, Robert Grimm.
 *    All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following
 * disclaimer in the documentation and/or other materials provided
 * with the distribution.
 *
 * 3. Neither name of Robert Grimm nor the names of his contributors
 * may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package one.eval;

import java.util.Collection;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * Implementation of a pair. 
 *
 * <p>A pair may optionally represent a literal, in which case the
 * pair itself and all objects (recursively) pointed to by the car and
 * cdr fields of the pair are unmodifiable. To be consistent with the
 * Java collections framework, all methods that modify such a pair
 * throw a <code>UnsupportedOperationException</code>. The {@link
 * #isLiteral()} method can be used to test whether a particular pair
 * instance is a literal. By default, all pairs are modifiable.
 * Furthermore, literal pairs can only be generated by other classes
 * in this package and, in particular, by the Scheme reader. Finally,
 * when a literal pair is copied, the copy is not a literal.</p>
 *
 * <p>Note that operations on pairs are not synchronized.</p>
 *
 * @author   &copy; Copyright 1998-2000 by Robert Grimm.
 *           Written by <a href="mailto:rgrimm@alum.mit.edu">Robert
 *           Grimm</a>.
 * @version  1.0
 */
public final class Pair implements java.io.Serializable, Cloneable {

  /** The empty list. The empty list is identical to <code>null</code>. */
  public  static final Pair EMPTY_LIST = null;

  private static final int HASH_RECURSION_LIMIT = 50;
  private static final int HASH_FACTOR          = 31;

  /**
   * The car field of a pair.
   *
   * @serial
   */
  Object car;

  /**
   * The cdr field of a pair.
   *
   * @serial
   */
  Object cdr;

  /**
   * Flag to indicate whether this pair is to be treated as a literal;
   * that is, as an unmodifiable pair. An unmodifiable pair must throw
   * a <code>UnsupportedOperationException</code> on all operations
   * that would modify its state. By default, all newly created pairs
   * are modifiable.
   *
   * @serial <code>true</code> iff the pair is to be treated as a
   *         literal.
   */
  boolean literal = false;

  /**
   * Create a new pair from the specified objects.
   *
   * @param  car  The car object.
   * @param  cdr  The cdr object.
   */
  public Pair(Object car, Object cdr) {
    this.car = car;
    this.cdr = cdr;
  }

  /**
   * Create a new pair from the specified objects.
   *
   * @param   car  The car object.
   * @param   cdr  The cdr object.
   * @return       A new pair with the specified car and cdr fields.
   */
  public static Pair cons(Object car, Object cdr) {
    return new Pair(car, cdr);
  }

  /**
   * Return the contents of the car field of this pair.
   *
   * @return  The car object of this pair.
   */
  public Object car() {
    return car;
  }

  /**
   * Return the contents of the cdr field of this pair.
   *
   * @return  The cdr object of this pair.
   */
  public Object cdr() {
    return cdr;
  }

  /**
   * Change the car field of this pair to point to the specified
   * object.
   *
   * @param   car  The new car of this pair.
   * @return       The old car of this pair.
   * @throws  UnsupportedOperationException
   *               Signals that this pair is a literal.
   */
  public Object setCar(Object car) {
    if (literal) throw new UnsupportedOperationException();
    Object oldCar = this.car;
    this.car      = car;
    return oldCar;
  }

  /**
   * Change the cdr field of this pair to point to the specified
   * object.
   *
   * @param   cdr  The new cdr of this pair.
   * @return       The old cdr of this pair.
   * @throws  UnsupportedOperationException
   *               Signals that this pair is a literal.
   */
  public Object setCdr(Object cdr) {
    if (literal) throw new UnsupportedOperationException();
    Object oldCdr = this.cdr;
    this.cdr      = cdr;
    return oldCdr;
  }

  /**
   * Return the result of applying the specified composition of {@link
   * #car()} and {@link #cdr()} operations on this pair and the
   * subsequent intermediate results. The template must be string
   * consisting of only 'a' and 'd' characters, where the letter 'a'
   * stands for a <code>car</code> operation and the letter 'd' stands
   * for a <code>cdr</code> operation. The template is
   * case-insensitive, and the order in which the <code>car</code> and
   * <code>cdr</code> operations are applied is from the end to the
   * beginning of the template.
   *
   * @param   template
   *             The template specifying the composition of
   *             <code>car</code> and <code>cdr</code> operations.
   * @result     The object resulting from applying the specified
   *             composition of <code>car</code> and <code>cdr</code>
   *             operations on this pair and subsequent intermediate
   *             results.
   * @throws  BadPairStructureException
   *             Signals that the specified operation cannot be
   *             applied on the current object because it is not
   *             a pair.
   * @throws  IllegalArgumentException
   *             Signals a malformed template.
   */
  public Object cxr(String template) throws BadPairStructureException {
    if ((null == template) || ("".equals(template))) {
      return this;
    }

    Object result = this;

    for (int i=template.length()-1; i>=0; i--) {
      if (! (result instanceof Pair)) {
        throw new BadPairStructureException("Not a pair", result);
      }

      char c = template.charAt(i);
      if (('a' == c) || ('A' == c)) {
        result = ((Pair)result).car;
      } else if (('d' == c) || ('D' == c)) {
        result = ((Pair)result).cdr;
      } else {
        throw new IllegalArgumentException("Malformed template \""
                                           + template + "\"");
      }
    }

    return result;
  }

  /**
   * Test whether this pair is a literal. If this pair is a literal,
   * all its elements are literals and recursively, if any of the
   * elements are pairs or vectors, their elements are also
   * literals. Furthermore, none of these elements can be a string
   * buffer.
   *
   * @see     Vector#isLiteral()
   *
   * @return  <code>true</code> iff this pair is a literal.

   */
  public boolean isLiteral() {
    return literal;
  }

  /**
   * Turn this pair into a literal. Sets the literal flag for this
   * pair to <code>true</code> and <em>recursively</em> calls the
   * method of the same name for the car and cdr if they are either a
   * vector or a pair.
   *
   * @throws  UnsupportedOperationException
   *              Signals that either the car or the cdr field point
   *              to a string buffer instead of an unmodifiable
   *              Java string.
   */
  void turnIntoLiteral() {
    if (literal) {
      return;
    } else {
      if (car instanceof Vector) {
        ((Vector)car).turnIntoLiteral();
      } else if (car instanceof Pair) {
        ((Pair)car).turnIntoLiteral();
      } else if (car instanceof StringBuffer) {
        throw new UnsupportedOperationException();
      }
      if (cdr instanceof Vector) {
        ((Vector)cdr).turnIntoLiteral();
      } else if (cdr instanceof Pair) {
        ((Pair)cdr).turnIntoLiteral();
      } else if (cdr instanceof StringBuffer) {
        throw new UnsupportedOperationException();
      }

      literal = true;
    }
  }

  /**
   * Test whether the cdr chain starting at this pair is circular.
   *
   * @return  <code>true</code> iff the cdr chain starting at this
   *          pair is circular.
   */
  public boolean isCircular() {
    /* See implementation comment for isList(). */
    Pair p1 = this;
    Pair p2 = this;

    while (true) {
      // Advance p2 first.
      Object o = p2.cdr;
      if (EMPTY_LIST == o) {
        return false;
      } else if (! (o instanceof Pair)) {
        return false;
      }

      o = ((Pair)o).cdr;
      if (EMPTY_LIST == o) {
        return false;
      } else if (! (o instanceof Pair)) {
        return false;
      }

      p2 = (Pair)o;

      // Advance p1. We know it hits a pair b/c p2 was already there.
      p1 = (Pair)p1.cdr;

      // Test for circularity.
      if (p1 == p2) return true;
    }
  }

  /**
   * Test whether the specified object is the empty list.
   *
   * @param   o  The object to test.
   * @return     <code>true</code> iff the specified object is
   *             the empty list.
   */
  public static boolean isNull(Object o) {
    return EMPTY_LIST == o;
  }

  /**
   * Test whether this pair starts a proper list. Returns
   * <code>true</code> if this pair is the start of a proper list;
   * that is, the cdrs of all pairs but the final pair in this list
   * point to another pair and the final cdr in this list is the empty
   * list (<code>EMPTY_LIST</code>).
   *
   * @return  <code>true</code> if this pair is the start of a 
   *          proper list.
   */
  public boolean isList() {
    /*
     * To determine whether this pair starts a proper list, we simply
     * follow the cdr chain until we hit the end. If the last element
     * is the empty list (that is, EMPTY_LIST), we return
     * true. Otherwise, we return false. To detect circular cdr
     * chains, we use two pointers. p2 advances two cdrs per round,
     * and p1 advances only one cdr per round. If, at the end of a
     * round, the two pointers are the same, we know that the list is
     * circular and return false.
     */
    Pair p1 = this;
    Pair p2 = this;

    while (true) {
      // Advance p2 first.
      Object o = p2.cdr;
      if (EMPTY_LIST == o) {
        return true;
      } else if (! (o instanceof Pair)) {
        return false;
      }

      o = ((Pair)o).cdr;
      if (EMPTY_LIST == o) {
        return true;
      } else if (! (o instanceof Pair)) {
        return false;
      }

      p2 = (Pair)o;

      // Advance p1. We know it hits a pair b/c p2 was already there.
      p1 = (Pair)p1.cdr;

      // Test for circularity.
      if (p1 == p2) return false;
    }
  }

  /**
   * Create a new list that is as long as the specified array and
   * contains all its elements in order. This method accepts an
   * <code>Object</code> argument instead of an <code>Object[]</code>
   * argument, so that it can also accept arrays with a primitive
   * component type.
   *
   * @param   a  The array of elements for the new list.
   * @return     A new list with the specified elements in order,
   *             or the empty list if <code>a</code> is of
   *             zero length.
   * @throws  IllegalArgumentException
   *             Signals that <code>a</code> is not an array.
   */
  public static Pair createList(Object a) {
    if (null == a) {
      return EMPTY_LIST;
    } else if (! a.getClass().isArray()) {
      throw new IllegalArgumentException("Not an array");
    }

    int len = java.lang.reflect.Array.getLength(a);

    if (0 == len) {
      return EMPTY_LIST;
    } else {
      Pair result = EMPTY_LIST;

      for (int i=len-1; i>=0; i--) {
        result = new Pair(java.lang.reflect.Array.get(a, i), result);
      }

      return result;
    }
  }

  /**
   * Create a new list that has as many elements as the specified
   * collection and contains all its elements in the order returned by
   * the specified collection's iterator.
   *
   * @param   c  The collection of objects for the new list.
   * @return     A new list with the specified objects in order
   *             of the specified collection's iterator, or the
   *             empty list if <code>c</code> has no elements.
   */
  public static Pair createList(Collection c) {
    if ((null == c) || c.isEmpty()) return EMPTY_LIST;

    Iterator iter = c.iterator();
    Object   o    = iter.next();  // Must have at least one element.
    Pair     head = new Pair(o, EMPTY_LIST);
    Pair     tail = head;

    while (iter.hasNext()) {
      o = iter.next();

      Pair p   = new Pair(o, EMPTY_LIST);
      tail.cdr = p;
      tail     = p;
    }

    return head;
  }

  /**
   * Create a new list that is a shallow copy of the list starting at
   * the specified pair. The new list is as long as the specified list
   * and contains all its elements in order. If any of the elements in
   * the specified list are also lists, they are not copied. The
   * specified list may be a proper or an improper list.
   *
   * @param   p  The pair starting the list to copy.
   * @return     A new list that is a shallow copy of the specified
   *             list, or the empty list if <code>p</code> is the
   *             empty list.
   * @throws  BadPairStructureException
   *             Signals that the list starting at the specified
   *             pair has a circular cdr chain.
   */
  public static Pair copyList(Pair p) throws BadPairStructureException {
    if (EMPTY_LIST == p) {
      return EMPTY_LIST;
    } else if (p.isCircular()) {
      throw new BadPairStructureException("Circular structure", p);
    }

    Pair q      = new Pair(p.car, EMPTY_LIST);
    Pair result = q;
    Pair tail   = q;

    do {
      Object o = p.cdr;
      if (EMPTY_LIST == o) {            // End of proper list.
        return result;
      } else if (o instanceof Pair) {   // Next element.
        p        = (Pair)o;
      } else {                          // End of improper list.
        tail.cdr = o;
        return result;
      }

      q        = new Pair(p.car, EMPTY_LIST);
      tail.cdr = q;
      tail     = q;
    } while (true);
  }
 
  /**
   * Return the length of the list starting at this pair.
   *
   * @return     The length of the list starting at this pair.
   * @throws  BadPairStructureException
   *             Signals that this pair does not start a proper
   *             list.
   */
  public int length() throws BadPairStructureException {
    /* See implementation comment for isList(). */
    int  l  = 1;
    Pair p1 = this;
    Pair p2 = this;

    while (true) {
      // Advance p2 first.
      Object o = p2.cdr;
      if (EMPTY_LIST == o) {
        return l;
      } else if (o instanceof Pair) {
        l++;
      } else {
        throw new BadPairStructureException("Not a list", this);
      }

      o = ((Pair)o).cdr;
      if (EMPTY_LIST == o) {
        return l;
      } else if (o instanceof Pair) {
        l++;
      } else {
        throw new BadPairStructureException("Not a list", this);
      }

      p2 = (Pair)o;

      // Advance p1. We know it hits a pair b/c p2 was already there.
      p1 = (Pair)p1.cdr;

      // Test for circularity.
      if (p1 == p2) {
        throw new BadPairStructureException("Not a list", this);
      }
    }
  }

  /**
   * Estimate the length of the cdr chain starting at this pair. For
   * proper lists, <code>estimateLength</code> functions exactly like
   * <code>length()</code> and returns the exact length.  For improper
   * lists (that is, lists whose last cdr points to an object other
   * than the empty list), it returns the length of the corresponding
   * proper list (that is, the list whose last cdr points to the empty
   * list) plus one. For circular cdr chains, it provides an estimate
   * of the number of unique elements in the list.
   *
   * @return  An estimate for the length of the cdr chain starting
   *          at this pair.
   */
  public int estimateLength() {
    /* See implementation comment for isList(). */
    int  l  = 1;
    Pair p1 = this;
    Pair p2 = this;

    while (true) {
      // Advance p2 first.
      Object o = p2.cdr;
      if (EMPTY_LIST == o) {
        return l;
      } else if (! (o instanceof Pair)) {
        return (l + 1);
      } else {
        l++;
      }

      o = ((Pair)o).cdr;
      if (EMPTY_LIST == o) {
        return l;
      } else if (! (o instanceof Pair)) {
        return (l + 1);
      } else {
        l++;
      }

      p2 = (Pair)o;

      // Advance p1. We know it hits a pair b/c p2 was already there.
      p1 = (Pair)p1.cdr;

      // Test for circularity.
      if (p1 == p2) {
        return l;
      }
    }
  }

  /**
   * Create a new list consisting of the elements of the individual
   * lists in the specified list of lists. Returns a list consisting
   * of the elements of the individual lists, which are the elements
   * of the specified list, in order. The resulting list is newly
   * allocated, except that it shares structure with the last element
   * in the specified list. The last element may actually be any
   * object; an improper list results if the last element is not a
   * proper list. If any of the individual lists is the empty list,
   * nothing is added to the resulting list for this individual list.
   *
   * @param   p   The pair starting the list of lists.
   * @return      A new list consisting of the elements of the
   *              individual lists in the specified list of lists
   *              followed by the last element in the specified list,
   *              or the single object if the specified list only
   *              contains one object, or the empty list if
   *              the specified list is the empty list.
   * @throws  BadTypeException
   *              Signals that an element in the specified list
   *              of lists is not a pair.
   * @throws  BadPairStructureException
   *              Signals that the specified list or any of the
   *              individual lists besides the last element is not
   *              a proper list.
   */
  public static Object append(Pair p)
    throws BadTypeException, BadPairStructureException {
    // Get the trivial cases out of the way.
    if (EMPTY_LIST == p) return p;
    int length = p.length(); // Signals if p does not start a proper list.
    if (1 == length) return p.car;

    // Skip any leading empty lists.
    while ((EMPTY_LIST == p.car) && (EMPTY_LIST != p.cdr)) {
      p = (Pair)p.cdr;
    }

    // Check that we didn't reach the last element.
    if (EMPTY_LIST == p.cdr) return p.car;

    /*
     * Now, do the real work.
     *
     * p          Pointer into the list of lists.
     * result     The head of the resulting list.
     * tail       The tail of the resulting list.
     * current    Pointer into the current list to copy.
     * q          Intermediate pair.
     * o          Intermediate object before being cast to a pair.
     */
    Pair result = EMPTY_LIST;
    Pair tail   = EMPTY_LIST;

    do {
      Object o = p.car;
      p        = (Pair)p.cdr; // Advance the list of lists.
      if (EMPTY_LIST == o) {
        continue;
      } else if (! (o instanceof Pair)) {
        throw new BadTypeException("Not a pair", o);
      }

      Pair current = (Pair)o;
      if (! current.isList()) {
        throw new BadPairStructureException("Not a list", current);
      }

      // Copy the current list.
      Pair q      = new Pair(current.car, EMPTY_LIST);
      if (EMPTY_LIST == result) {
        result    = q;
        tail      = q;
      } else {
        tail.cdr  = q;
        tail      = q;
      }

      do {
        o         = current.cdr;
        if (EMPTY_LIST == o) break;
        current   = (Pair)o;
        q         = new Pair(current.car, EMPTY_LIST);
        tail.cdr  = q;
        tail      = q;
      } while(true);

    } while(EMPTY_LIST != p.cdr);

    // Add last element to result.
    tail.cdr = p.car;

    return result;
  }

  /**
   * Return a newly allocated list consisting of the elements of
   * the list starting with this pair in reverse order.
   *
   * @return     A new list consisting of the elements of the list
   *             starting at this pair in reverse order.
   * @throws  BadPairStructureException
   *             Signals that this pair does not start a proper
   *             list.
   */
  public Pair reverse() throws BadPairStructureException {
    if (! isList()) {
      throw new BadPairStructureException("Not a list", this);
    }

    Pair current = this;
    Pair result  = EMPTY_LIST;

    do {
      result  = new Pair(current.car, result);
      current = (Pair)current.cdr;
    } while (EMPTY_LIST != current);

    return result;
  }

  /**
   * Return the sublist of the list starting at this pair by omitting
   * the number of specified elements. Omits the first <code>i</code>
   * elements from the list starting at this pair. This pair is the
   * 0<sup><font size="-1">th</font></sup> pair of the list starting
   * at this pair.
   *
   * @param   i  The number of elements to omit from the list starting
   *             at this pair.
   * @return     The <code>i</code><sup><font size="-1">th</font></sup>
   *             pair of the list starting at this pair.
   * @throws  BadPairStructureException
   *             Signals that this pair does not start a proper
   *             list.
   * @throws  IndexOutOfBoundsException
   *             Signals that the list starting at this pair is
   *             too short.
   */
  public Pair getListTail(int i) throws BadPairStructureException {
    Object o = this;

    while (i > 0) {
      if (EMPTY_LIST == o) {
        throw new IndexOutOfBoundsException();
      } else if (! (o instanceof Pair)) {
        throw new BadPairStructureException("Not a list", this);
      }
      o = ((Pair)o).cdr;
      i--;
    }
    
    return (Pair)o;
  }

  /**
   * Return the <code>i</code><sup><font size="-1">th</font></sup>
   * element of the list starting at this pair. Omits the first
   * <code>i</code> elements from the list starting at this pair and
   * returns the car of the resulting sublist. The first element of
   * this list is the 0<sup><font size="-1">th</font></sup> element.
   *
   * @param   i  The number of elements to omit from the list starting
   *             at this pair before the element whose car to return.
   * @return     The <code>i</code><sup><font size="-1">th</font></sup>
   *             element of the list starting at this pair.
   * @throws  BadPairStructureException
   *             Signals that this pair does not start a proper
   *             list.
   * @throws  IndexOutOfBoundsException
   *             Signals that the list starting at this pair is
   *             too short.
   */
  public Object getListRef(int i) throws BadPairStructureException {
    Pair p = getListTail(i);

    if (EMPTY_LIST == p) {
      throw new IndexOutOfBoundsException();
    } else {
      return p.car;
    }
  }

  /**
   * Return the first sublist of the list starting at this pair whose
   * car is equivalent to the specified element according to the
   * specified equivalence relation. Returns the empty list if the
   * specified element does not appear in the list starting at this
   * pair.
   *
   * @param   element
   *             The element to search for.
   * @param   eqv
   *             The equivalence relation to compare the specified
   *             element with the list elements.
   * @return     The sublist of the list starting at this pair whose
   *             car is equivalent to the specified element, or
   *             <code>EMPTY_LIST</code> if the specified element does
   *             not appear in the list.
   * @throws  BadPairStructureException
   *             Signals that this pair does not start a proper
   *             list.
   */
  public Pair member(Object element, Equivalence eqv)
    throws BadPairStructureException {
    if (! isList()) {
      throw new BadPairStructureException("Not a list", this);
    }

    Pair p = this;
    do {
      if (eqv.compare(p.car, element)) return p;
      p = (Pair)p.cdr;
    } while (EMPTY_LIST != p);

    return EMPTY_LIST;
  }

  /**
   * Return the first pair of the association list starting at this
   * pair whose car is equivalent to the specified element according
   * to the specified equivalence relation. Returns the empty list if
   * the specified element does not appear in any pair in the
   * association list starting at this pair.
   *
   * @param   element
   *             The element to search for.
   * @param   eqv
   *             The equivalence relation to compare the specified
   *             element with the association list's car fields.
   * @return     The pair in the association list whose car is
   *             equivalent to the specified element, or
   *             <code>EMPTY_LIST</code> if the specified element does
   *             not appear in the association list.
   * @throws  BadPairStructureException
   *             Signals that this pair does not start an association
   *             list.
   */
  public Pair assoc(Object element, Equivalence eqv)
    throws BadPairStructureException {
    if (! isList()) {
      throw new BadPairStructureException("Not an association list", this);
    }

    Pair p = this;
    do {
      Object o = p.car;
      if (! (o instanceof Pair)) {
        throw new BadPairStructureException("Not an association list", this);
      } else if (eqv.compare(((Pair)o).car, element)) {
        return ((Pair)o);
      }
      p = (Pair)p.cdr;
    } while (EMPTY_LIST != p);

    return EMPTY_LIST;
  }

  /**
   * Normalize the specified pair. If the specified pair is the empty
   * list, this method returns a boolean representing false instead of
   * the empty list. Otherwise, the pair itself is returned. This
   * method is useful for normalizing the results of the {@link
   * #member} and {@link #assoc} operations which, in departure from
   * the member and assoc operations defined in &sect;6.3.2 of
   * R<sup><font size="-1">5</font></sup>RS, return the empty list if
   * no match was found.
   *
   * @param   p  The pair to normalize.
   * @return     <code>#f</code>, that is, <code>Boolean.FALSE</code>,
   *             if <code>p</code> is the empty list. Otherwise,
   *             <code>p</code>.
   */
  public static Object normalize(Pair p) {
    if (EMPTY_LIST == p) {
      return Boolean.FALSE;
    } else {
      return p;
    }
  }

  /**
   * Compare this pair to the specified object for equality. This
   * method returns <code>true</code> if the specified object also is
   * a pair and both the cars and the cdrs are equal according to
   * their <code>equals()</code> methods. Note that this equality test
   * is not the same as the Scheme predicate <code>equal?</code>.
   *
   * @param   o  The object to compare to.
   * @return     <code>true</code> if this pair equals the specified
   *             object.
   */
  public boolean equals(Object o) {
    if (this == o) return true;
    if (! (o instanceof Pair)) return false;
    
    Pair one = this;
    Pair two = (Pair)o;

    do {
      // Compare cars.
      if (null == one.car) {
        if (null != two.car) {
          return false;
        }
      } else {
        if (! one.car.equals(two.car)) {
          return false;
        }
      }

      // Look at cdrs.
      Object o1 = one.cdr;
      Object o2 = two.cdr;

      if (o1 instanceof Pair) {
        if (o2 instanceof Pair) {
          one = (Pair)o1;
          two = (Pair)o2;
        } else {
          return false;
        }
      } else {
        if (null == o1) {
          return (o1 == o2);
        } else {
          return o1.equals(o2);
        }
      }
    } while (true);
  }

  /**
   * Return a hash code for this pair.
   *
   * @return  A hash code for this pair.
   */
  public int hashCode() {
    int  hashCode = 0;
    Pair p        = this;

    do {
      hashCode = 31 * hashCode + ((null == p.car)? 0 : p.car.hashCode());

      Object o = p.cdr;

      if (o instanceof Pair) {
        p = (Pair)o;
      } else if (null == o) {
        return hashCode;
      } else {
        return (31 * hashCode + o.hashCode());
      }
    } while (true);
  }

  /**
   * Return an array containing all elements of the list starting
   * at this pair in order.
   *
   * @return     The array containing all elements of the list starting
   *             at this pair.
   * @throws  BadPairStructureException
   *             Signals that this pair does not start a proper list.
   */
  public Object[] toArray() throws BadPairStructureException {
    int      l = length();
    Object[] a = new Object[l];
    
    Pair p = this;
    int  i = 0;
    do {
      a[i++] = p.car;

      p = (Pair)p.cdr;
    } while (EMPTY_LIST != p);

    return a;
  }

  /**
   * Return a Java collections framework list containing all elements
   * of the proper list starting at this pair in order.
   *
   * @return      A Java collections framework list containing all
   *              elements of this list.
   * @throws   BadPairStructureException
   *              Signals that this pair does not start a proper
   *              list.
   */
  public ArrayList toArrayList() throws BadPairStructureException {
    int       l = length();
    ArrayList a = new ArrayList(l);

    Pair p = this;
    do {
      a.add(p.car);

      p = (Pair)p.cdr;
    } while (EMPTY_LIST != p);

    return a;
  }

  /**
   * Cast the specified object to a pair. The empty list is not
   * considered a pair by this method.
   *
   * @param   o  The object to cast.
   * @return     The specified object as a pair.
   * @throws  BadTypeException
   *             Signals that <code>o</code> is not a pair.
   */
  public static Pair toPair(Object o) throws BadTypeException {
    if (o instanceof Pair) {
      return (Pair)o;
    } else {
      throw new BadTypeException("Not a pair", o);
    }
  }

  /**
   * Cast the specified object to a pair and ensure that it
   * is modifiable. The empty list is not considered a pair
   * by this method.
   *
   * @param   o  The object to cast.
   * @return     The specified object as a modifiable pair.
   * @throws  BadTypeException
   *             Signals that <code>o</code> is not a pair.
   * @throws  BadArgumentException
   *             Signals that <code>o</code> is not
   *             modifiable.
   */
  public static Pair toModifiablePair(Object o)
    throws BadTypeException, BadArgumentException {
    Pair p = toPair(o);
    if (p.literal) {
      throw new BadArgumentException("Constant pair", o);
    } else {
      return p;
    }
  }

}
